package com.dynamicPlanning;

/**
 * 假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
 * 1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
 * 2.如果不能获取到任何利润，请返回0
 * 3.假设买入卖出均无手续费
 *
 * 输入：[8,9,2,5,4,7,1]
 * 返回值：5
 * 说明：在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，
 * 不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。
 */
public class MaxProfit {
    public static void main(String[] args) {
        int[] prices = new int[]{8,9,2,5,4,7,1};
        System.out.println(maxProfit3(prices));
    }
    /**
     * 暴力求解发
     */
    public static int maxProfit1(int[] prices){
        int maxProfit1 = 0;
        for (int i = 0; i < prices.length-1; i++) {
            for (int j = i+1; j < prices.length; j++) {
                maxProfit1 = Math.max(prices[j]-prices[i],maxProfit1);
            }
        }
        return maxProfit1;
    }

    /**
     * 贪心算法
     */
    public static int maxProfit2(int[] prices){
        int minVal = prices[0], profit = 0;
        //{8,9,2,5,4,7,1}
        for (int i = 1; i < prices.length; ++i) {
            if (minVal > prices[i]) {
                minVal = prices[i];
            }
            profit = Math.max(profit, prices[i] - minVal);
        }
        return profit;
    }

    /**
     * 动态规划
     * 我们来定义一个二维数组dp[length][2]，其中dp[i][0]表示第i+1天（i是从0开始的）结束的时候没持有股票的最大利润，
     * dp[i][1]表示第i+1天结束的时候持有股票的最大利润，因为持有股票肯定是花钱买来的利润暂时是负的。
     * 如果我们要求第i+1天结束的时候没持有股票的最大利润dp[i][0]，那么会有两种情况。
     *  第一种情况就是第i+1天我们即没买也没卖，那么最大利润就是第i天没持有股票的最大利润dp[i-1][0]。
     *  第二种情况就是第i+1天我们卖了一支股票，那么最大利润就是第i天持有股票的最大利润（这个是负的，并且也不一定是第i天开始持有的，有可能在第i天之前就已经持有了）加上第i+1天卖出股票的最大利润，dp[i-1][1]+prices[i]。
     */
    public static int maxProfit3(int[] prices){
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        //边界条件
        dp[0][0]= 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            //递推公式
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);//当天没有持有股票的最大收益
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);//记录股票的最低价格
        }
        //毋庸置疑，最后肯定是手里没持有股票利润才会最大，也就是卖出去了
        return dp[length - 1][0];
    }

    /**
     * 我们看到上面二维数组中计算当天的最大利润只和前一天的利润有关，所以没必要使用二维数组，
     * 只需要使用两个变量即可，一个表示当天持有股票的最大利润，一个表示当天没持有股票的最大利润，代码如下。
     */
    public int maxProfit4(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int hold = -prices[0];//持有股票
        int noHold = 0;//不持有股票
        for (int i = 1; i < length; i++) {
            //递推公式
            noHold = Math.max(noHold, hold + prices[i]);
            hold = Math.max(hold, -prices[i]);
        }
        //毋庸置疑，最后肯定是手里没持有股票利润才会最大
        //也就是卖出去了
        return noHold;
    }

    public static int maxProfit5(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int cur = 0;
        int max = cur;
        //{8,9,2,5,4,7,1}
        for (int i = 1; i < length; i++) {
            //这地方把prices[i]改为 prices[i] - prices[i - 1]即可
            cur = Math.max(cur, 0) + prices[i] - prices[i - 1];
            //记录最大值
            max = Math.max(max, cur);
        }
        return max;
    }
}
